This application is related to co-pending U.S. Patent application entitled xe2x80x9cA METHOD AND APPARATUS FOR GENERATING ONE TIME PADS SIMULTANEOUSLY IN SEPARATE ENCRYPTION/DECRYPTION SYSTEMSxe2x80x9d made by the same inventors, assigned to the same assignee and filed concurrently with this application. The disclosure of the above referenced application is incorporated by reference into this application.
1. Field of the Invention
This invention relates generally to encryption and decryption of digital messages or file representations, more specifically, to a hybrid scheme for encrypting and decrypting a high security encrypted message or file representation using a one time random number pad where the pad transmission is multiplexed with the encrypted data and the pad determines the multiplexing pattern.
2. Description of the Prior Art
Encryption and decryption devices are desired within the communications industry. As reliance on electronic banking, internet e-mail and other purely electronic communications increase, there is an increasing need for secure communications which cannot be broken, even with high computation power and heavy investments in technology.
This need is presently being filled by such algorithms as DES (Data Encryption Standard) and RSA (Rivest-Shamir-Adleman) encryption techniques. For the purpose of discussion, these will be referred to as xe2x80x9cshort keyxe2x80x9d techniques. While these techniques are robust and allow for variable keys, they are still potentially subject to defeat by application of repetitive analysis to decode the cipher which is cycled many times in a typical message.
A technique which is hypothetically undefeatable is the one time pad technique. Unfortunately it is also impractical in its application. The one time pad technique uses a pad which is a perfectly random set of numbers the same size as the message transmitted. This pad is combined with the message data (typically by an exclusive-OR operation) to produce the encrypted data. Since the pad is truly random, there is no relationship of the output data from this operation to the input data that was provided. The impracticality of the one time pad technique stems from several factors: 1) The encrypted data and pad are twice as large as the original message; and 2) The security requirement for the pad is as great as the security requirement of the message; 3) The recipient needs the pad to decode the message; and 4) The pad can only be used once or repetitive analysis could reveal the pad.
In order to use a one time pad in a practical application, a need exists to transmit the pad in a fashion as secure as the message itself. A method is also needed so that the recipient does not have to have foreknowledge of the pad in order to decode the message.
The present invention fills these needs by creating a hybrid encoding scheme which is reliant on another encryption technique such as DES or RSA, but only exposes a DES or RSA key for the initial portion of the transmission of the pad. As such, it overcomes the limitations of both the one time pad technique and the drawbacks of DES and RSA. The one time pad is transmitted after being encrypted by DES, RSA or other algorithm and interleaved with the message, but the encrypted pad itself is used to determine the interleave pattern. Thus an attempt to decipher the message or pad requires a deciphering of the interleave between the message and the pad, which raises the difficulty far beyond the difficulty of deciphering a DES or RSA encoded message.
The short decryption key must be known to the recipient before the message can be decoded. A scheme such as the Diffie-Hellman Key Exchange algorithm could be used in combination with the present invention.
In accordance with one embodiment of the present invention, it is an object of the present invention to provide a method and apparatus for encrypting and decrypting messages and files.
It is another object of the present invention to provide a method and apparatus for encrypting and decrypting messages and files which uses a one time pad and securely encodes the one time pad along with the message.
It is another object of the present invention to provide a method and apparatus for encrypting and decrypting messages and files which encodes a one time pad by a short key technique and interleaves the one time pad in a random pattern with the actual message data so as to make it undecipherable except by knowing the short key, which is protected by the interleaving pattern.
In accordance with one embodiment of the present invention, a hybrid one-time pad encryption device is disclosed. The device uses a random number generator to generate a pad for each message that is to be encrypted which is the same size as the message. In the preferred embodiment this is accomplished by generating a random sequence at the same rate as an input message data stream. The random number sequence comprises the one time pad and is encoded using a secure technique such as DES or RSA. The input message data is combined with the unencoded one time pad by an exclusive OR and the output data stream is made by interleaving the output of this exclusive OR (the encrypted input data) with the encoded one time pad. The selection of interleave is made by the unencoded one time pad.
In accordance with another embodiment of the present invention, a hybrid one time pad decryption device is disclosed. The decryption device can decode the above encoded output data produced by the encryption device. A demultiplexer routes the encrypted data stream to either the time pad decoder or the pad decrypter, which uses the complement of the DES, RSA or other encryption scheme used to encode the one time pad above, to decode the one time pad. The output of this pad decrypter is returned to the control input of the demultiplexer to reverse the interleaving process that was carried out during encryption. The decoded pad is then combined in the pad decoder with the encrypted data stream using another exclusive OR operation to undo the encryption of the message data that was combined with the pad data in the encrypter. The operation of the present invention is not restricted to the use of exclusive OR as the encryption operator for the one time pad encoder and decoder. Any symmetric operation could be used.
In accordance with the above embodiments, the methods for transmitting and receiving encrypted digital messages or storing and retrieving encrypted data are also disclosed. A random sequence of numbers is generated which serves as the one time pad and is combined with the input data to produce an encrypted data stream. The one time pad itself is encrypted by means of the above mentioned DES, RSA or other xe2x80x9cshort keyxe2x80x9d encryption means to produce an encrypted pad and then the encrypted pad and the encrypted data stream are interleaved and output as a single data stream, with the interleave selection made by the unencrypted one time pad.
The foregoing and other objects, features, and advantages of the invention will be apparent from the following, more particular, description of the preferred embodiment of the invention, as illustrated in the accompanying drawings.